package com.skh.string;

import java.util.Arrays;

/**
 * @Author: skh
 * @Date: 2019/7/9 18:39
 * @Description: 字符的最短距离
 */
public class ShortestToChar {

    /*
    给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
说明:

字符串 S 的长度范围为 [1, 10000]。
C 是一个单字符，且保证是字符串 S 里的字符。
S 和 C 中的所有字母均为小写字母。
     */

    /*
    思路:只要扫描一遍字符串，每当遇到字符C，我们就分别向左、右进行更新到C的最短距离即可，直到左、右遇到了边界或者字符C
     */
    public int[] shortestToChar(String S, char C) {
        int length = S.length();
        int[] result = new int[length];

        for (int center = 0; center < length; center++) {
            //查找字符C的位置,跳过非C的字符
            while (center < length && S.charAt(center) != C) {
                center++;
            }

            if (center != length) {
                result[center] = 0;
                int left = center-1;
                int right = center+1;
                //向左扩展更新最短距离
                while (left >= 0 && S.charAt(left)!=C) {
                    if (result[left] == 0) {
                        result[left] = center-left;
                    }else {
                        result[left] = Math.min(result[left], center - left);
                    }
                    left--;
                }
                //向右扩展更新最短距离
                while (right < length && S.charAt(right) != C) {
                    if (result[right] == 0) {
                        result[right] = right - center;
                    }else {
                        result[right] = Math.min(result[right], right - center);
                    }
                    right++;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        ShortestToChar shortestToChar = new ShortestToChar();
        int[] ints = shortestToChar.shortestToChar("loveleetcode", 'e');
        System.out.println(Arrays.toString(ints));

    }
}
